Sequences and Summations

Sets are unordered collection of elements S={a,b,}S=\{a, b,\cdots\}
Sequences are ordered lists of elements

SS is usually taken to be a set of the form {k,k+1,k+2,}Z\{k, k+1, k+2, \cdots\} \subseteq \mathbb{Z}

Here k = initial index (usually 0,1 )k\text{ = initial index (usually 0,1 )}

The set of numbers is most often R= real numbers\mathbb{R}=\text{ real numbers}

a sequence then is range(f)={f(k),f(k+1),f(k+2),}range(f)=\{f(k), f(k+1), f(k+2), \cdots\}

We usually wite ax=f(n)a_{x}=f(n) for nkn \geqslant k and range(f)={ak,ak+1,,an,}={an}n=kNrange(f)=\left\{a_{k}, a_{k+1}, \cdots, a_{n}, \cdots\right\}=\left\{a_{n}\right\}_{n=k}^{N} ana_{n} is called the general term

(NZ(N \in Z or N=+)N=+\infty) general term

S= index setS=\text{ index set}

If SS is a finite subset of Z\mathbb{Z}, then the sequence range(f)range(f) is a finite sequence
If SS is an infinite subset of Z\mathbb{Z}, then the resulting sequence is is an infinite sequence

There are some special sequences that often arise...

Geometric Progression

Here S={0,1,2,}=Z+{0}S=\{0,1,2, \cdots\}=\mathbb{Z}^{+} \cup\{0\}
and f(n)=an=arnwherea,rR f(n)=a_{n}=a r^{n}\quad where\quad a,r\in\mathbb{R}

The sequence is

{an}n=0+={a,ar,ar2,ar3,ar4,,arn,} \left\{a_{n}\right\}_{n=0}^{+\infty}=\left\{a, a \cdot r, a \cdot r^{2}, a \cdot r^{3}, a \cdot r^{4}, \cdots, a \cdot r^{n}, \cdots\right\}

aa is called the initial term and rr is called the common ratio

Geometric Series (Finite)
G_{n}&=a+a r+\cdots+a r^{n}\\ &=\sum_{k=0}^{n} a r^{k}= \begin{cases}\displaystyle{\frac{a\left(r^{n+1}-1\right)}{r-1}} &, r \neq 1 \\ (n+1)a &, r=1\end{cases}

Poof Case i) r=1r=1.

Gn=k=0na(1)k=k=0na(1)=ak=0n(1)=a(1+1++1n+1 terms =a(n+1). \begin{aligned} G_{n}=\sum_{k=0}^{n} a(1)^{k}=\sum_{k=0}^{n} a(1)=a \sum_{k=0}^{n}(1) & =a(\underbrace{1+1+\cdots+1}_{n+1} \text { terms } \\ & =a(n+1) . \end{aligned}

Case ii) r1r \neq 1

Gn=a+ar+ar2++arnrGn=ar+ar2++arn+arn+1rGnGn=(r1)Gn=arn+1a=a(rn+11) thus Gn=a(rn+11)r1 \begin{aligned} & G_{n}=a+a r+a r^{2}+\cdots+a r^{n} \\ & r G_{n}=a r+a r^{2}+\cdots+a r^{n}+a r^{n+1} \\ & \therefore r G_{n}-G_{n}=(r-1) G_{n}=a r^{n+1}-a=a\left(r^{n+1}-1\right) \text {. } \\ & \text { thus } G_{n}=\frac{a\left(r^{n+1}-1\right)}{r-1} \end{aligned}

bdg-secondaryproof

Let\qquad S_n&=\sum^n_{j=m}ar^j\\

To compute SS, first multiply both sides of the equality by rr and then manipulate the resulting sum as follows:

rS_n&=r\sum^n_{j=0}ar^j\qquad\textcolor{hotpink}{\textrm{multiply both sides by $r$}}\\ &=\sum^n_{j=0}ar^{j+1}\qquad\textcolor{hotpink}{\textrm{by the distributive property}}\\ &=\sum^{n+1}_{k=1}ar^{k}\qquad\textcolor{hotpink}{\textrm{Shifting the index by $k=j+1$}}\\ &=ar^1 + ar^2 + ar^3 + , \cdots , ar^n + ar^{n+1}\\ &=\left(\sum^{n+1}_{k=1}ar^{k}\right)+(ar^{n+1}-a)\qquad\textcolor{hotpink}{\textrm{Isolate $n+1$ term but add $k=0$ term}}\\ &=S_n+(ar^{n+1}-a)\qquad\textcolor{hotpink}{\textrm{Substitute back S for the summation formula}}\\

We see thus that rSn=Sn+(arn+1a)rS_n = S_n + (ar^{n+1}-a) so solving for SnS_n if r1r\ne 1, then
Sn=arn+1ar1\displaystyle S_n = \frac{ar^{n+1} - a}{r - 1}

For r=1r=1 then the Sn=j=0narj=j=0naS_n=\sum^n_{j=0}ar^j=\sum_{j=0}^na

Arithmetic Progression

Here S={0,1,2,}=Z+{0}S=\{0,1,2, \ldots\}=\mathbb{Z}^+ \cup\{0\}
and f(n)=a+nd f(n)=a+n \cdot d
where a,dRa, d \in \mathbb{R}
the sequence is

{an}n=0+={a,a+d,a+2d,,a+nd,} \left\{a_{n}\right\}_{n=0}^{+\infty}=\{a, a+d, a+2 d, \cdots, a+n d, \cdots\}

a is called the initial term and dd is called the common difference

Sequences of the form a1,a2,...,ana_1, a_2, ... , a_n are often used in computer science where these finite sequences are called strings denoted by a1a2...ana_1 a_2 ... a_n The length of a string is the number of terms in this string the empty string is denoted by λ\lambda which of course has no terms and hence has length zero

An=k=0n(a+dk)=(n+1)(2a+nd)2 A_{n}=\sum_{k=0}^{n}(a+d k)=\frac{(n+1)(2 a+n d)}{2}

Poof

An=k=0n(a+dk)=k=0na+k=0ndk=ak=0ni+dk=1nk=(n+1)a+d(k=1nk) \begin{aligned} A_{n} & =\sum_{k=0}^{n}(a+d k)=\sum_{k=0}^{n} a+\sum_{k=0}^{n} d k \\ & =a \sum_{k=0}^{n} i+d \sum_{k=1}^{n} k \\ & =(n+1) a+d\left(\sum_{k=1}^{n} k\right) \end{aligned}

Fact

k=1nk=1+2++n=n(n+1)2 \sum_{k=1}^{n} k=1+2+\cdots+n=\frac{n(n+1)}{2}

Thus

An=(n+1)a+dn(n+1)2=(n+1)(2a+nd)2 \begin{aligned} A_{n} & =(n+1) a+d \frac{n(n+1)}{2} \\ & =\frac{(n+1)(2 a+n d)}{2} \end{aligned}

Harmonic Progression

Here S={1,2,}=Z+S=\{1, 2, \cdots\}=\mathbb{Z}^+ and f(n)=1nf(n)=\frac{1}{n}
The sequence is

{an}n=1={1,12,13,,1n,} \left\{a_{n}\right\}_{n=1}^{\infty}=\left\{1, \frac{1}{2}, \frac{1}{3}, \cdots, \frac{1}{n}, \cdots\right\}

Recurrence Relation

Before we specified sequences by providing explicit formulas for their terms
but there are other ways to specify a sequence

Some useful Sequences

some useful sequences

Summations

am,a(m+1),,ana_m,a_(m+1),\cdots ,a_n, from the sequence \Setan\Set{a_n}

We use the notation

j=mnaj=j=mnaj=m j  nnaj \displaystyle\sum^n_{j=m}a_j = \textstyle\sum^n_{j=m}a_j = \displaystyle\sum^n_{m\ \le j\ \le\ n}a_j

reads as the sum from j = m to j = n of aj\textit{sum from j = m to j = n of }a_j

Variable jj is called the index of summation or dummy index you can define it as any variable as below shows

j=mnaj=i=mnai=k=mnak \sum^n_{j=m}a_j = \sum^n_{i=m}a_i = \sum^n_{k=m}a_k

Variable mm is called the lower limit or the initial index
Variable nn is called the upper limit or terminal index

(summation-formulae)=

Some Useful Summation Formulae

Sum Closed Form
k=0nark (r0)\displaystyle{\sum^n_{k=0}ar^k\ (r\ne 0)} refproof arn+1ar1\displaystyle{\frac{ar_{n+1}-a}{r-1}}
k=1nk\displaystyle{\sum^n_{k=1}k} n(n+1)2\displaystyle{\frac{n(n+1)}{2}}
k=2nk2\displaystyle{\sum^n_{k=2}k^2} n(n+1)(2n+1)6\displaystyle{\frac{n(n+1)(2n+1)}{6}}
k=2nk3\displaystyle{\sum^n_{k=2}k^3} n2(n+1)24\displaystyle{\frac{n^2(n+1)^2}{4}}
k=0xk,x<1\displaystyle{\sum^\infty_{k=0}x^k, \mid x\mid \lt 1} 11x\displaystyle{\frac{1}{1-x}}
k=1xk,x<1\displaystyle{\sum^\infty_{k=1}x^k, \mid x\mid \lt 1} 1(1x)2\displaystyle{\frac{1}{(1-x)^2}}

Double Sums

Sometimes we want to sum a matrix of numbers
To do this we use a double sum

(a11a12a1nan1an2ann)k,l=1nakl=k=1nl=1naklSo first sum all l terms then sum all k terms Ex k=13l=24(k+1)l2=k=13{(k+1)4+(k+1)9+(k+1)16}=k=1329(k+1)=29(k=13(k+1))=29[2+3+4]=29×9=261 \begin{pmatrix} a_{11} &a_{12} &\cdots& &a_{1n} \\ \vdots &\vdots &\cdots& &\vdots \\ a_{n1} &a_{n2} &\cdots& &a_{nn} \\ \end{pmatrix}\\ \newline \sum^n_{k,l=1}a_{kl}\quad =\quad \sum^n_{k=1}\sum^n_{l=1}a_{kl} \newline \newline \color{violet}{\text{So first sum all $l$ terms then sum all $k$ terms}}\\ \begin{aligned} & \text { Ex } \quad \sum_{k=1}^3 \sum_{l=2}^4(k+1) l^2 \\ &=\sum_{k=1}^3\{(k+1) 4+(k+1) 9+(k+1) 16\} \\ &=\sum_{k=1}^3 29(k+1)=29\left(\sum_{k=1}^3(k+1)\right) \\ &=29[2+3+4]=29 \times 9=261 \end{aligned}

Special Finite Arithmetic Sequence

(1) k=1nk=n(n+1)2=1+2++n\displaystyle\sum_{k=1}^{n} k=\frac{n(n+1)}{2}=1+2+\cdots+n

Proof: k=0n(a+dk)\sum_{k=0}^{n}(a+dk)

(proof:special-finite-sum-1)=

Proof: k=1nk\sum_{k=1}^{n}k

This is a Arithmetic Sequence

S=\text{Let }\sum^n_{k=1} &= 1+2+3+\cdots+(n-1)+n\\ \text{(backwards) }S &= n + (n-1) + (n-2) + \cdots + 2 + 1\\ \newline \therefore \quad 2 S &=(n+1)+(n+1)+\cdots+(n+1)(n \text { terms }) \\ & =n(n+1) \\ \newline \therefore\ \quad S &=\frac{n(n+1)}{2}

(2) k=1nk2=n(n+1)(2n+1)6=1+4+9++n2\displaystyle\sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}=1+4+9+\cdots+n^{2}

(3) k=1nk3=[n(n+1)2]2=1+8+27++n3\displaystyle\sum_{k=1}^{n} k^{3}=\left[\frac{n(n+1)}{2}\right]^{2}=1+8+27+\cdots+n^{3}

bdg-dangerLater We will prove (2) & (3) using principle of mathematical induction

Infinite Series

Infinite series are important in many branches of mathematics, especially mathematical analysis

An infinite series is a summation of an infinite number of terms

Actually the sum of an infinite number of terms is not defined

However we can talk about these infinite sums in the context of wether or not they converge to a sum by looking at the sequence of partial sums

Let {an}n=0+\left\{a_{n}\right\}_{n=0}^{+\infty} be an infinite sequence of real numbers.

Let {Sn}n=0+\left\{S_{n}\right\}_{n=0}^{+\infty} be the sequence of partial sums of {an}n=0+\left\{a_{n}\right\}_{n=0}^{+\infty},

sn=k=0nak=a0+a1++an s_{n}=\sum_{k=0}^{n} a_{k}=a_{0}+a_{1}+\cdots+a_{n}

Before we go any further we must talk about the limit of a sequence

Let {Sn}n=0+\left\{S_{n}\right\}_{n=0}^{+\infty} be a sequence of real numbers (infinite).

We say {Sn}n=0+\left\{S_{n}\right\}_{n=0}^{+\infty} converges to LL

or

limn+Sn=L iff ε>0,N(ε)Z+ such thatSnL<ε,nN \begin{aligned} & \displaystyle\lim _{n \rightarrow+\infty} S_{n}=L \quad \text { iff }\\ \newline & \forall \varepsilon>0,\quad\exists N(\varepsilon) \in \mathbb{Z}^{+} \text { such that}\\ & \left|S_{n}-L\right|<\varepsilon,\quad \forall n \geqslant N \end{aligned}

What this means is that the larger that nn gets the chosen sns_{n} gets to LL
and we say that SnLS_{n} \rightarrow L as x+x \rightarrow+\infty

If there is no number LL such that SxLS_{x} \rightarrow L as n+n \rightarrow+\infty we say that the sequence {Sn}n=0+\left\{S_{n}\right\}_{n=0}^{+\infty} diverges

(12)(12)

Two important limits

(1) limn+xn=0\displaystyle\lim _{n \rightarrow+\infty} x^{n}=0 if x<1|x|<1

(2) limn+1n=0\displaystyle\lim _{n \rightarrow+\infty} \frac{1}{n}=0

We have already discussed (2) before with the calculator if n becomes large enough the answer converges to 0

We prove (1) using Bernoulli's inequality

1+nh(1+h)n,n=0,1,2,,h>1 \begin{gathered} 1+nh \leqslant(1+h)^{n},\quad \forall n=0,1,2, \ldots,\quad h>-1 \end{gathered}

We will see a proof of this inequality later by proof by mathematical induction

limn+1n=0\displaystyle\lim _{n \rightarrow+\infty} \frac{1}{n}=0 if x<1|x|<1
Proof by Cases

case (i) 0<x<10<x<1.

Write x=11+h,h>0x=\displaystyle\frac{1}{1+h}, h>0

then xn=1(1+h)n11+xh1a>1bx^{n}=\displaystyle\frac{1}{(1+h)^{n}} \leqslant \frac{1}{1+x h} \quad \begin{array}{ll} & \rightarrow \frac{1}{a}>\frac{1}{b}\end{array}

<1nh <\frac{1}{n h}

Thus xn0=xn=1(1+h)n<1nh<ε\left|x^{n}-0\right|=\left|x^{n}\right|=\frac{1}{(1+h)^{n}}<\frac{1}{n h}<\varepsilon if nh>1εn h>\frac{1}{\varepsilon}, ie x>1hεx>\frac{1}{h \varepsilon} oR x1hεx \geqslant\left\lceil\frac{1}{h \varepsilon}\right\rceil (13)

for any ε>0\varepsilon>0.

Thus ε>0,xx<ε\forall \varepsilon>0, \quad x^{x} \mid<\varepsilon \quad whenever

n1nε,x=11+h n \geqslant\left\lceil\frac{1}{n \varepsilon}\right\rceil \quad, x=\frac{1}{1+h}

case (ii) x=0,xn=00x=0, x^{n}=0 \rightarrow 0 as x+x \rightarrow+\infty

case (iii) 1<x<0-1<x<0

then 0<x<10<-x<1

and x=11+h,h>0-x=\frac{1}{1+h}, h>0

so

xn0=xx=1(1+h)n<1xh\left|x^{n}-0\right|=\left|x^{x}\right|=\frac{1}{(1+h)^{n}}<\frac{1}{x h} as before

Exevise Show (1)(1) is really "if" by showing x1limn+xn0|x| \geqslant 1 \Rightarrow \lim _{n \rightarrow+\infty} x^{n} \neq 0

Returning to infinite series,

We say n=0+an\sum_{n=0}^{+\infty} a_{n} converges to LL

and wite n=0+an=L\sum_{n=0}^{+\infty} a_{n}=L if

limn+Sn=limn+(k=0nak)=L \lim _{n \rightarrow+\infty} S_{n}=\lim _{n \rightarrow+\infty}\left(\sum_{k=0}^{n} a_{k}\right)=L

(14)

Thus an infinite series converges the sequence of partial sums converges to a limit.

If n=0+an\sum_{n=0}^{+\infty} a_{n} is not convergent,

ie, limn+Sn\lim _{n \rightarrow+\infty} S_{n} does not exist,

we say n=0+an\sum_{n=0}^{+\infty} a_{n} is divergent.

The Infinite Geometric Series

k=0+ark is convergent if and only if r<1 \sum_{k=0}^{+\infty} a r^{k} \quad \text { is convergent if and only if }|r|<1

Since Gn=k=0nark=a(rn+11)r1G_{n}=\displaystyle\sum_{k=0}^{n} a r^{k}=\frac{a\left(r^{n+1}-1\right)}{r-1}

If r<1|r|<1, then limn+Gn=limn+a(rn+11)r1\displaystyle\lim _{n \rightarrow+\infty} G_{n}=\lim _{n \rightarrow+\infty} \frac{a\left(r^{n+1}-1\right)}{r-1}

=a(01)r1=a1r \begin{aligned} & =\frac{a(0-1)}{r-1} \\ & =\frac{a}{1-r} \end{aligned}

Thus for r<1,k=0+ark=a1r\displaystyle|r|<1, \sum_{k=0}^{+\infty} a r^{k}=\frac{a}{1-r}

Exercise: 0.999=1 0.999 \cdots=1

Exercise use this result to show 0.999=1 0.999 \cdots=1

0.9999=910+9100+=k=1910k=9(k=1(110)k)=9(110+1102++110n+110n+1+)=910(1+110+1102+)=910k=0(110)k=91011110=9101(910)=1 \begin{aligned} 0.9999 \cdots = \frac{9}{10} + \frac{9}{100} + \cdots & =\sum_{k=1}^{\infty} \frac{9}{10^{k}} \\ & =9\left(\sum_{k=1}^{\infty}\left(\frac{1}{10}\right)^{k}\right) \\ & =9\left(\frac{1}{10}+\frac{1}{10^{2}}+\cdots+\frac{1}{10^{n}}+\frac{1}{10^{n+1}}+\cdots\right) \\ & =\frac{9}{10}\left(1+\frac{1}{10}+\frac{1}{10^{2}}+\cdots\right) \\ & =\frac{9}{10} \sum_{k=0}^{\infty}\left(\frac{1}{10}\right)^{k}=\frac{9}{10} \frac{1}{1-\frac{1}{10}} \\ & =\frac{9}{10} \cdot \frac{1}{\left(\frac{9}{10}\right)}=1 \end{aligned}

We have shown only the "If" part of own statement.

To prove the "only if" part, we note

for r=1,Gn=a(x+1)+r=1, G_{n}=a(x+1) \rightarrow+\infty as n+n \rightarrow+\infty

so {Gn}n=0+\left\{G_{n}\right\}_{n=0}^{+\infty} does not have a limit (it diverges to ++\infty ) and k=0+a(1)k\sum_{k=0}^{+\infty} a(1)^{k} is divergent,

If r>1|r|>1, one can show that limn+(rn+1)\lim _{n \rightarrow+\infty}\left(r^{n+1}\right) does not exist since if r>1r>1, these terms get larger and larger positively, while if r<1,rn+1r<-1, r^{n+1} gets larger and larger in absolute value and it switches from positive to negative and so cant have a limit

EXERCISE: What happens when r=1r=-1?

Principle of Mathematical Induction

Consider a formal sequence of propositional functions {P(n)}n=1+\{P(n)\}_{n=1}^{+\infty}.

We want to be able to prove that the proposition nP(n)\forall n P(n) is True where the universe of discourse for the universal quantifier, \forall, is Z+\mathbb{Z}^{+}.

As some examples of such a proposition we have the 3 summation formulae from before,

k=1nk=n(n+1)2,n+Z+\sum_{k=1}^{n} k=\frac{n(n+1)}{2}, \forall n+\mathbb{Z}^{+} k=1nk2=n(n+1)(2n+1)6,nZ+\sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}, \forall n \in \mathbb{Z}^{+} k=1nk3=[n(n+1)2]2,nZ+\sum_{k=1}^{n} k^{3}=\left[\frac{n(n+1)}{2}\right]^{2}, \forall n \in \mathbb{Z}^{+}

We prove such universally quantified propositions using the principle of mathematical induction

Steps

principle of mathematical induction has 2 steps.

Step 1 Basis step; prove P(1)P(1) is true.

Step 2 Inductive step; prove that the proposition
k(P(k)P(k+1))(k1) \forall k(P(k) \rightarrow P(k+1)) \quad(k \geq 1) is true

We will prove the validity of PMI. later

For now consider some examples. At the same time we will be proving useful and important results

Prove statement 1

Exercise Prove statement eqinduction-1 above. [ Note, we already gave a direct proof  by showing P(n) is T, for all n]\left[\begin{array}{c}\text { Note, we already gave a direct proof } \\ \text { by showing } P(n) \text { is } T \text {, for all } n\end{array}\right]

Let P(n)P(n) be the statement

k=1nk=n(n+1)2=f(n) \sum_{k=1}^{n} k=\frac{n(n+1)}{2}=f(n)
Basis Step

P(1):k=11k=1,f(1)=1(1+1)2=1\displaystyle P(1): \sum_{k=1}^{1} k=1, f(1)=\frac{1(1+1)}{2}=1

P(1)\therefore P(1) is true

Inductive step

assume Pk(k)P_{k}(k) is tue, kZ+(k1)k \in \mathbb{Z}^{+}(k \geqslant 1)

That is l=1kl=k(k+1)2=f(k)\displaystyle\sum_{l=1}^{k} l=\frac{k(k+1)}{2}=f(k).

We show now that P(k+1)P(k+1) is true,

ie, k=1k+1l=f(k+1)=(k+1)(k+2)2\displaystyle\sum_{k=1}^{k+1} l=f(k+1) =\frac{(k+1)(k+2)}{2}

But

l=1k+1l==1kl+(k+1)=k(k+1)2+(k+1), by hypothesis. =(k+1)(k2+1)=(k+1)(k+2)2=f(k+1) \begin{aligned} \sum_{l=1}^{k+1} l&=\sum_{\ell=1}^{k} l+(k+1) \\ & =\frac{k\cdot (k+1)}{2}+(k+1), \text { by hypothesis. } \\ & =(k+1)\left(\frac{k}{2}+1\right) \\ & =\frac{(k+1)(k+2)}{2}=f(k+1) \end{aligned}

Thus P(k)P(k+1),kZ+P(k) \rightarrow P(k+1), \forall k \in \mathbb{Z}^{+}

Hence by PMI,k=1nk=n(n+1)2,nZ+\displaystyle P M I, \sum_{k=1}^{n} k=\frac{n(n+1)}{2}, \forall n \in \mathbb{Z}^{+}

Prove Statement 2

Prove eqinduction-2 above: k=1nk2=n(n+1)(2n+1)6,nZ\displaystyle\sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}, \forall n \in \mathbb{Z} =f(x)=f(x)

Basis Step
n=1.k=1k2=1;f(1)=1(2)(3)6=1 n=1 . \quad \sum_{k=1} k^{2}=1 ; f(1)=\frac{1(2)(3)}{6}=1

Thus P(1)P(1) is true

Inductive Step

Assume P(k)P(k) is true, kZ+(k1)k \in \mathbb{Z}^{+}(k \geqslant 1)

Thenl=1k+1l2=l=1kl2+(k+1)2=k(k+1)(2k+1)6+(k+1)2, by hypothesis=(k+1)[k(2k+1)6+k+1]=(k+1)[2k2+k+6(k+1)6]=(k+1)[2k2+7k+66]=(k+1)6[2k2+4k+3k+6]=(k+1)6[2k(k+2)+3(k+2)]=(k+1)(k+2)(2k+3)6=f(k+1) \begin{aligned} Then\quad\sum_{l=1}^{k+1} l^{2}&=\sum_{l=1}^{k} l^{2}+(k+1)^{2}\\ \newline & =\frac{k(k+1)(2k+1)}{6}+(k+1)^{2} \text {, by hypothesis} \\ \newline & =(k+1)\left[\frac{k(2 k+1)}{6}+k+1\right] \\ \newline & =(k+1)\left[\frac{2k^{2}+k+6(k+1)}{6}\right] \\ \newline & =(k+1)\left[\frac{2k^{2}+7k+6}{6}\right] \\ \newline & =\frac{(k+1)}{6}\left[2k^{2}+4k + 3k+6\right] \\ \newline & =\frac{(k+1)}{6}[2 k(k+2)+3(k+2)] \\ \newline & =\frac{(k+1)(k+2)(2k+3)}{6}=f(k+1) \end{aligned}

Thus kZ+,P(k)P(k+1)\forall k \in \mathbb{Z}^{+},\quad P(k) \rightarrow P(k+1) is true
and by the principle of mathematical induction
P(n)P(n) is true, n+Z+\forall n+\mathbb{Z}^{+}

Common Errors

The Harmonic Progression

Recall the Harmonic Progression {an}n=1\left\{a_{n}\right\}_{n=1}^{\infty} where an=1na_{n}=\frac{1}{n}.

Even though,

limn+an=limn+1n=0 \lim _{n \rightarrow+\infty} a_{n}=\lim _{n \rightarrow+\infty} \frac{1}{n}=0 \text {, }

the Harmonic series n=1+1n=1+12+13++1n+\displaystyle\sum_{n=1}^{+\infty} \frac{1}{n}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}+\cdots is divergent
The smaller and smaller bit added infinitely often add up to ++\infty !

We will use the principle of mathematical induction to help prove this fact

bdg-secondaryProof

Basis step

n=1H21=1+12=f(1)H21f(1) \begin{aligned} & n=1 \\ & H_{2^{1}}=1+\frac{1}{2}=f(1) \quad \therefore H_{2^1} \geqslant f(1) \end{aligned}

Inductive Step

assume H2k1+k2,kZ+H_{2^{k}} \geqslant 1+\frac{k}{2}, \forall k \in \mathbb{Z}^{+}

Then

H2k+1=k=12k+11k=r=12k1r+k=2k+12k+11r1+k2+12k+1+12k+2++12k+1=1+k2+12k+1+12k+2++12k+2k \begin{aligned} H_{2^{k+1}} & =\sum_{k=1}^{2^{k+1}} \frac{1}{k}=\sum_{r=1}^{2^{k}} \frac{1}{r}+\sum_{k=2^{k}+1}^{2^{k+1}} \frac{1}{r} \\ & \geqslant 1+\frac{k}{2}+\frac{1}{2^{k}+1}+\frac{1}{2^{k}+2}+\cdots+\frac{1}{2^{k+1}} \\ & =1+\frac{k}{2}+\frac{1}{2^{k}+1}+\frac{1}{2^{k}+2}+\cdots+\frac{1}{2^{k}+2^{k}} \end{aligned} 1+k2+{12k+2k++2k terms 2k+2k}( make the  bottom bigger  fraction get  smaller )=1+k2+2k12k+1=1+k2+12=1+k+12=f(k+1) \begin{aligned} & \geqslant 1+\frac{k}{2}+\left\{\frac{1}{2^{k}+2^{k}}+\cdots+\frac{2^{k} \text { terms }}{2^{k}+2^{k}}\right\} \quad\left(\begin{array}{l} \text { make the } \\ \text { bottom bigger } \\ \text { fraction get } \\ \text { smaller } \end{array}\right) \\ & =1+\frac{k}{2}+2^{k} \cdot \frac{1}{2^{k+1}}=1+\frac{k}{2}+\frac{1}{2}=1+\frac{k+1}{2}=f(k+1) \end{aligned}

Thus by P,M.1. H2n1+n2,nZ+H_{2} n \geqslant 1+\frac{n}{2}, \forall n \in \mathbb{Z}^{+}

Now the sequence

{Hn}n=1\left\{H_{n}\right\}_{n=1}^{\infty} is an "increasing" sequence

because Hn+1=Hn+1n+1>HnH_{n+1}=H_{n}+\frac{1}{n+1}>H_{n}.

Also the subsequence

{H2n}x=1\left\{H_{2^{n}}\right\}_{x=1}^{\infty} clearly, in view of

the lemma, has

limx+H2x=+ \lim _{x \rightarrow+\infty} H_{2 x}=+\infty

These two facts allow us to assent that

limn+Hn=+ and the  \lim _{n \rightarrow+\infty} H_{n}=+\infty \text { and the }

hamonic series is divergent

Exerciser) Use PMI to prove that 3/22n1,xZ+3 / 2^{2 n}-1, \forall x \in \mathbb{Z}^{+}

  1. Prove summation formula (3)

P351 #32 3n3+2nn13 \mid n^{3}+2 n \quad \forall n \geqslant 1

23

P(n):3n3+2nP(n): 3 \mid n^{3}+2 n \quad R.T.P. n1P(n)\quad \forall n \geqslant 1 P(n) is the

  1. Basis step

Let n=1,n3+2n=1+2=3+3/3n=1, n^{3}+2 n=1+2=3+3 / 3

P(1)\therefore P(1) is true

  1. Inductive Step

want to show

k1P(k)P(k+1)\forall k \geqslant 1 \quad P(k) \rightarrow P(k+1) \quad is tue

Assume 31k3+2k31 k^{3}+2 k ie assume P(k)P(k) is the

Then (k0+1)3+2(k+1)=k3+3k2+3k+1\left(k^{0}+1\right)^{3}+2(k+1)=k^{3}+3 k^{2}+3 k+1

=k3+2k+3k+2=k3+2k divisible by +3(k2+k+1) divisible by 3 \begin{aligned} = & k^{3}+2 k+3 k+2 \\ = & \frac{k^{3}+2 k}{\text { divisible }_{\text {by }}}+\frac{3\left(k^{2}+k+1\right)}{\text { divisible by } 3} \end{aligned}

by hypothein

P(k+1)\therefore P(k+1) is tue